package q236;

import java.util.Stack;

/**
 * 236. 二叉树的最近公共祖先
 */
public class Solution236 {
    TreeNode p, q;

    Stack<TreeNode> ps = new Stack<>();
    Stack<TreeNode> qs = new Stack<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.q = q;
        this.p = p;
        Stack<TreeNode> stack = new Stack<>();
        dfs(root, stack);
        while (!ps.isEmpty()) {
            TreeNode n = ps.pop();
            if (qs.contains(n)) {
                return n;
            }
        }
        return null;
    }

    public void dfs(TreeNode node, Stack<TreeNode> stack) {
        if (node == null) return;
        stack.push(node);
        if (node == p) ps.addAll(stack);
        if (node == q) qs.addAll(stack);
        if (!ps.isEmpty() && !qs.isEmpty()) {
            return;
        }
        dfs(node.left, stack);
        dfs(node.right, stack);
        stack.pop();
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

}
